/*------------------------------------------------------------------------
 *
 * geqo_pmx.c
 *
 * 部分匹配交叉 [PMX] 例程；
 * 根据 Goldberg & Lingle 的 PMX 操作符
 * (Proc Int'l Conf on GA's)
 *
 * src/backend/optimizer/geqo/geqo_pmx.c
 *
 *-------------------------------------------------------------------------
 */

/* 贡献者：
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
   *  Martin Utesch				 * 自动控制研究所		   *
   =							 = 矿业与技术大学 =
   *  utesch@aut.tu-freiberg.de  * 德国弗赖贝格				   *
   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
 */

/* pmx 算法采自 Genitor : */
/*************************************************************/
/*															 */
/*	Copyright (c) 1990										 */
/*	Darrell L. Whitley										 */
/*	计算机科学系									         */
/*	科罗拉多州立大学									     */
/*															 */
/*	特此允许复制本程序的全部或部分以进行自由分发。作者的姓名  */
/*	及本版权声明必须包含在任何复制中。 */
/* geqo_copy
 *
 *	 将一个基因复制到另一个
 *
 */
/*															 */
/*************************************************************/

#include "postgres.h"
#include "optimizer/geqo_random.h"
#include "optimizer/geqo_recombination.h"

#if defined(PMX)

/* pmx
 *
 * 部分匹配交叉
 */
void pmx(PlannerInfo *fc_root, Gene *fc_tour1, Gene *fc_tour2, Gene *fc_offspring, int fc_num_gene)
{
	int		   *fc_failed = (int *) palloc((fc_num_gene + 1) * sizeof(int));
	int		   *fc_from = (int *) palloc((fc_num_gene + 1) * sizeof(int));
	int		   *fc_indx = (int *) palloc((fc_num_gene + 1) * sizeof(int));
	int		   *fc_check_list = (int *) palloc((fc_num_gene + 1) * sizeof(int));

	int			fc_left,
				fc_right,
				fc_temp,
				fc_i,
				fc_j,
				fc_k;
	int			fc_mx_fail,
				fc_found,
				fc_mx_hold;


/* 没有变异，因此启动 pmx 替换算法 */
/* 初始化 failed[]，from[]，check_list[] */
	for (fc_k = 0; fc_k < fc_num_gene; fc_k++)
	{
		fc_failed[fc_k] = -1;
		fc_from[fc_k] = -1;
		fc_check_list[fc_k + 1] = 0;
	}

/* 定位交叉点 */
	fc_left = geqo_randint(fc_root, fc_num_gene - 1, 0);
	fc_right = geqo_randint(fc_root, fc_num_gene - 1, 0);

	if (fc_left > fc_right)
	{
		fc_temp = fc_left;
		fc_left = fc_right;
		fc_right = fc_temp;
	}


/* 将 tour2 复制到子代 */
	for (fc_k = 0; fc_k < fc_num_gene; fc_k++)
	{
		fc_offspring[fc_k] = fc_tour2[fc_k];
		fc_from[fc_k] = DAD;
		fc_check_list[fc_tour2[fc_k]]++;
	}

/* 将 tour1 复制到子代 */
	for (fc_k = fc_left; fc_k <= fc_right; fc_k++)
	{
		fc_check_list[fc_offspring[fc_k]]--;
		fc_offspring[fc_k] = fc_tour1[fc_k];
		fc_from[fc_k] = MOM;
		fc_check_list[fc_tour1[fc_k]]++;
	}


/* pmx 主要部分 */

	fc_mx_fail = 0;

/* STEP 1 */

	for (fc_k = fc_left; fc_k <= fc_right; fc_k++)
	{							/* 遍历 tour1-2 中的所有元素 */

		if (fc_tour1[fc_k] == fc_tour2[fc_k])
			fc_found = 1;			/* 在 tour2 中查找匹配 */

		else
		{
			fc_found = 0;			/* 替换元素 */

			fc_j = 0;
			while (!(fc_found) && (fc_j < fc_num_gene))
			{
				if ((fc_offspring[fc_j] == fc_tour1[fc_k]) && (fc_from[fc_j] == DAD))
				{

					fc_check_list[fc_offspring[fc_j]]--;
					fc_offspring[fc_j] = fc_tour2[fc_k];
					fc_found = 1;
					fc_check_list[fc_tour2[fc_k]]++;
				}

				fc_j++;
			}
		}

		if (!(fc_found))
		{						/* 无法替换基因 */
			fc_failed[fc_mx_fail] = (int) fc_tour1[fc_k];
			fc_indx[fc_mx_fail] = fc_k;
			fc_mx_fail++;
		}
	}							/* ... for */


/* STEP 2 */

	/* 检查是否有任何基因无法被替换 */
	if (fc_mx_fail > 0)
	{
		fc_mx_hold = fc_mx_fail;

		for (fc_k = 0; fc_k < fc_mx_hold; fc_k++)
		{
			fc_found = 0;

			fc_j = 0;
			while (!(fc_found) && (fc_j < fc_num_gene))
			{

				if ((fc_failed[fc_k] == (int) fc_offspring[fc_j]) && (fc_from[fc_j] == DAD))
				{
					fc_check_list[fc_offspring[fc_j]]--;
					fc_offspring[fc_j] = fc_tour2[fc_indx[fc_k]];
					fc_check_list[fc_tour2[fc_indx[fc_k]]]++;

					fc_found = 1;
					fc_failed[fc_k] = -1;
					fc_mx_fail--;
				}

				fc_j++;
			}
		}						/* ... for	 */
	}							/* ... if	 */


/* STEP 3 */

	for (fc_k = 1; fc_k <= fc_num_gene; fc_k++)
	{

		if (fc_check_list[fc_k] > 1)
		{
			fc_i = 0;

			while (fc_i < fc_num_gene)
			{
				if ((fc_offspring[fc_i] == (Gene) fc_k) && (fc_from[fc_i] == DAD))
				{
					fc_j = 1;

					while (fc_j <= fc_num_gene)
					{
						if (fc_check_list[fc_j] == 0)
						{
							fc_offspring[fc_i] = (Gene) fc_j;
							fc_check_list[fc_k]--;
							fc_check_list[fc_j]++;
							fc_i = fc_num_gene + 1;
							fc_j = fc_i;
						}

						fc_j++;
					}
				}				/* ... if	 */

				fc_i++;
			}					/* 结束 while */
		}
	}							/* ... for	 */

	pfree(fc_failed);
	pfree(fc_from);
	pfree(fc_indx);
	pfree(fc_check_list);
}

#endif							/* 定义（PMX） */
